{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Knight Moves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minKnightMoves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #进击的骑士"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个坐标可以从 <code>-infinity</code>&nbsp;延伸到&nbsp;<code>+infinity</code>&nbsp;的 <strong>无限大的</strong>&nbsp;棋盘上，你的 <strong>骑士&nbsp;</strong>驻扎在坐标为&nbsp;<code>[0, 0]</code>&nbsp;的方格里。</p>\n",
    "\n",
    "<p>骑士的走法和中国象棋中的马相似，走 “日” 字：即先向左（或右）走 1 格，再向上（或下）走 2 格；或先向左（或右）走 2 格，再向上（或下）走 1 格。</p>\n",
    "\n",
    "<p>每次移动，他都可以按图示八个方向之一前进。</p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2018/10/12/knight.png\" style=\"width: 250px; height: 250px;\" /></p>\n",
    "\n",
    "<p>返回 <em>骑士前去征服坐标为&nbsp;<code>[x, y]</code>&nbsp;的部落所需的最小移动次数</em> 。本题确保答案是一定存在的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 2, y = 1\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>[0, 0] → [2, 1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 5, y = 5\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>[0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>-300 &lt;= x, y &lt;= 300</code></li>\n",
    "\t<li><code>0 &lt;= |x| + |y| &lt;= 300</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-knight-moves](https://leetcode.cn/problems/minimum-knight-moves/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-knight-moves](https://leetcode.cn/problems/minimum-knight-moves/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n1', '5\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "\n",
    "        if x==0 and y==0:\n",
    "            return 0\n",
    "\n",
    "        def getNbgr(x, y):\n",
    "            ans_dict = dict()\n",
    "            ans = set()\n",
    "            dist = x*x + y*y\n",
    "            for dx, dy in [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)]:\n",
    "                nx, ny = x+dx, y+dy\n",
    "                new_dist = nx*nx + ny*ny\n",
    "                if new_dist <= 8:\n",
    "                    ans.add((nx, ny))\n",
    "                else:\n",
    "                    ans_dict[new_dist] = (nx, ny)\n",
    "            min_key = min(ans_dict.keys())\n",
    "            ans.add(ans_dict[min_key])\n",
    "            print(ans)\n",
    "            return ans\n",
    "        \n",
    "        bfs = [(x, y)]\n",
    "        step=0\n",
    "        while bfs:\n",
    "            nxt_bfs = set([])\n",
    "            for x, y in bfs:\n",
    "                nbgrs = getNbgr(x, y)\n",
    "                for nx, ny in nbgrs:\n",
    "                    if nx == 0 and ny== 0:\n",
    "                        return step+1\n",
    "                    else:\n",
    "                        nxt_bfs.add((nx, ny))\n",
    "            step +=1\n",
    "            bfs = nxt_bfs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        if (x, y) == (0, 0):\n",
    "            return 0\n",
    "        x = abs(x)+10\n",
    "        y = abs(y)+10\n",
    "        directions = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2),\n",
    "        (-2, -1), (-2, 1), (-1, 2)]\n",
    "        valid = [[1 for _ in range(320)] for _ in range(320)]\n",
    "        valid[10][10] = 0\n",
    "        nodes = [(10, 10)]\n",
    "        steps = 0\n",
    "        while nodes:\n",
    "            steps += 1\n",
    "            new_nodes = []\n",
    "            for node in nodes:\n",
    "                nx, ny = node\n",
    "                for dx, dy in directions:\n",
    "                    new_x, new_y = nx+dx, ny+dy \n",
    "                    if new_x<0 or new_x>=320:\n",
    "                        continue\n",
    "                    if new_y<0 or new_y>=320:\n",
    "                        continue\n",
    "                    if not valid[new_x][new_y]:\n",
    "                        continue\n",
    "                    new_node = (new_x, new_y)\n",
    "                    # if new_node in visit_set:\n",
    "                    #     continue\n",
    "                    if new_node==(x, y):\n",
    "                        return steps\n",
    "                    new_nodes.append(new_node)\n",
    "                    valid[new_x][new_y] = 0\n",
    "                    # visit_set.add(new_node)\n",
    "            nodes = new_nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(x: int, y: int) -> int:\n",
    "            if x + y == 0:\n",
    "                return 0\n",
    "            if x + y == 2:\n",
    "                return 2\n",
    "            \n",
    "            return min(dfs(abs(x - 1), abs(y - 2)), dfs(abs(x - 2), abs(y - 1))) + 1\n",
    "        \n",
    "        return dfs(abs(x), abs(y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        if x == 0 and y == 0:\n",
    "            return 0\n",
    "        stack = [(0,0,0)]\n",
    "        visited = set([(0,0)])\n",
    "        nearest = float('inf')\n",
    "        def dis(a, b):\n",
    "            return abs(a-x) + abs(b-y)\n",
    "        while stack:\n",
    "            \n",
    "            p1, p2, steps = stack.pop(0)\n",
    "            nearest = min(nearest, dis(p1,p2))\n",
    "            if dis(p1, p2) - nearest > 25:\n",
    "                continue\n",
    "            for ioo,joo in [(2,1),(1,2)]:\n",
    "                for m1 in [1,-1]:\n",
    "                    for m2 in [1,-1]:\n",
    "                        i = ioo * m1 + p1\n",
    "                        j = joo * m2 + p2\n",
    "                        if x == i and y == j:\n",
    "                            return steps+1\n",
    "                        else:\n",
    "                            if (i, j) not in visited:\n",
    "                                stack.append((i, j, steps+1))\n",
    "                                visited.add((i, j))\n",
    "\n",
    "        \n",
    "                            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        x, y = abs(x), abs(y)\n",
    "        visited = {}\n",
    "        visited[(0,0)] = 0\n",
    "        q = deque()\n",
    "        q.append((0,0))\n",
    "        steps = 0 \n",
    "        moves = [\n",
    "            (1,2), (2,1), (-2, -1), (-2, 1), (2, -1), (-1, 2), (-1,-2), (1, -2)\n",
    "        ]\n",
    "        while len(q) > 0:\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                i, j = q.popleft()\n",
    "                visited[(i,j)] = steps\n",
    "                if i == x and j == y:\n",
    "                    return steps \n",
    "                for dx, dy in moves:\n",
    "                    if (i+dx,j+dy) not in visited:\n",
    "                        if -2 <= i+dx <= x + 2 and -2<= j + dy <= y + 2:\n",
    "                            visited[(i+dx,j+dy)] = -1\n",
    "                            q.append((i+dx, j+dy))\n",
    "            steps += 1\n",
    "        # for i in range(bound + 3):\n",
    "        #     print(dp[i])\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# moves = [\n",
    "#             (1,2), (2,1), (-2, -1), (-2, 1), (2, -1), (-1, 2), (-1,-2), (1, -2)\n",
    "#         ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        directions = [[-1,2], [-1,-2], [-2,1], [-2,-1], [1,2], [1,-2], [2,1], [2,-1]]\n",
    "        if x==0 and y==0:\n",
    "            return 0\n",
    "        x, y = abs(x), abs(y)\n",
    "\n",
    "        queue = [(0, 0)]\n",
    "        vis = set()   \n",
    "        vis.add((0, 0))\n",
    "        step = 0\n",
    "        while queue:\n",
    "            sz = len(queue)\n",
    "            step += 1\n",
    "            for _ in range(sz):\n",
    "                i, j = queue.pop(0)\n",
    "                for dx, dy in directions:\n",
    "                    nx, ny = i + dx, j + dy   \n",
    "                    if (nx, ny) not in vis:\n",
    "                        if -5<=nx<=x+5 and -5<=ny<=y+5:\n",
    "                            if nx==x and ny==y:      \n",
    "                                return step\n",
    "                            else:\n",
    "                                queue.append((nx, ny))\n",
    "                                vis.add((nx, ny)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        x, y = abs(x), abs(y)\n",
    "        min_heap = PriorityQueue()\n",
    "        best_stat = {}\n",
    "\n",
    "        min_heap.put((max(x, y)//2, 0, 0, 0))\n",
    "        best_stat[(0, 0)] = 0\n",
    "\n",
    "        while not min_heap.empty():\n",
    "            _, payload, i, j = min_heap.get()\n",
    "\n",
    "            if i == x and j == y:\n",
    "                return payload\n",
    "\n",
    "            for ii, jj in [(1, 2), (-1, 2), (1, -2), (-1, -2), (2, 1), (-2, 1), (2, -1), (-2, -1)]:\n",
    "                new_i, new_j = i + ii, j + jj\n",
    "                if (new_i, new_j) not in best_stat or payload+1 < best_stat[(new_i, new_j)]:\n",
    "                    min_heap.put( (payload + max(abs(new_i-x), abs(new_j-y))//2, payload+1, new_i, new_j) )\n",
    "                    best_stat[(new_i, new_j)] = payload+1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        if x == 0 and y == 0:\n",
    "            return 0\n",
    "        x = abs(x)\n",
    "        y = abs(y)\n",
    "        directions = [[-2, -1], [-1, -2], [1, -2], [2, -1], [1, 2], [2, 1], [-2, 1], [-1, 2]]\n",
    "\n",
    "        visited1 = set((0, 0))\n",
    "        visited2 = set((x, y))\n",
    "        queue1 = [(0, 0)]\n",
    "        queue2 = [(x, y)]\n",
    "        step = 0\n",
    "\n",
    "        while True:\n",
    "            if len(queue1) > len(queue2):  # 要求1短。\n",
    "                visited1, queue1, visited2, queue2 = visited2, queue2, visited1, queue1\n",
    "\n",
    "            new_queue1 = []\n",
    "            for i, j in queue1:\n",
    "                if (i, j) in visited2:\n",
    "                    return step\n",
    "                for dire in directions:\n",
    "                    new_i, new_j = i + dire[0], j + dire[1]\n",
    "                    if new_i >= -1 and new_j >= -1 and (new_i, new_j) not in visited1:\n",
    "                        visited1.add((new_i, new_j))\n",
    "                        new_queue1.append((new_i, new_j))\n",
    "            queue1 = new_queue1\n",
    "\n",
    "            step += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        x = abs(x)\n",
    "        y = abs(y)\n",
    "        x_low = -50\n",
    "        x_high = x+50\n",
    "        y_low = -50\n",
    "        y_high = y+50\n",
    "        visit = {(0, 0)}\n",
    "        stack = deque([[0, 0, 0]])\n",
    "        while stack:\n",
    "            i, j, d = stack.popleft()\n",
    "            if (i, j) == (x, y):\n",
    "                return d\n",
    "            for a, b in [[i-2, j+1], [i-2, j-1], [i-1, j-2], [i-1, j+2], \n",
    "                         [i+2, j+1], [i+2, j-1], [i+1, j-2], [i+1, j+2]]:\n",
    "                if (a, b) not in visit and x_low<=a<=x_high and y_low<=b<=y_high:\n",
    "                    stack.append([a, b, d+1])\n",
    "                    visit.add((a, b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        dirs = [(2, 1), (1, 2), (-2, 1), (-1,2), (2, -1), (1, -2), (-2, -1), (-1,-2)]\n",
    "        dis = abs(x) + abs(y)\n",
    "        visited = set()\n",
    "        # print(dis, x, y)\n",
    "        visited.add((0, 0))\n",
    "        def startFrom(path, length):\n",
    "            nonlocal dis\n",
    "            # print(path)\n",
    "            newpath = []\n",
    "            for loc in path:\n",
    "                locX, locY = loc[0], loc[1]\n",
    "                print('$24513', locX, locY, x, y)\n",
    "                if locX == x and locY == y:\n",
    "                    return length\n",
    "                for i in dirs:\n",
    "                    if abs(locX + i[0] - x) + abs(locY + i[1] - y) > dis + 3 or (locX + i[0], locY + i[1]) in visited: \n",
    "                        continue\n",
    "                    # print(\"fyl#\", dis, abs(locX + i[0]-x) + abs(locY + i[1] - y), (locX + i[0], locY + i[1]))\n",
    "                    newpath.append((locX + i[0], locY + i[1]))\n",
    "                    visited.add((locX + i[0], locY + i[1]))\n",
    "                    dis = min(dis, abs(locX + i[0]-x) + abs(locY + i[1] - y))\n",
    "                    if dis == 0:\n",
    "                        return length + 1\n",
    "            return startFrom(newpath, length + 1)\n",
    "        return startFrom([(0, 0)], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        q = collections.deque([(0,0)])\n",
    "        N = 1000 #500都不行\n",
    "        board = [[False]*N for _ in range(N)]\n",
    "\n",
    "        target = (x,y)\n",
    "\n",
    "        if (0,0) == target:\n",
    "            return 0\n",
    "\n",
    "        \n",
    "        res = 0\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                x, y = q.popleft()\n",
    "\n",
    "                for i,j in ((x-1, y-2), (x-1, y+2), (x+1, y-2), (x+1, y+2), (x+2, y+1), (x+2, y-1), (x-2,y-1), (x-2,y+1)):\n",
    "                    if board[i][j] == False:\n",
    "                        if (i,j) == target:\n",
    "                            return res+1\n",
    "                        board[i][j] = True\n",
    "                        q.append((i,j))\n",
    "            res += 1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "directions=[(1,2),(1,-2),(-1,2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1)]\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        #start_x=0 start_y=0\n",
    "        if (x,y)==(0,0):\n",
    "            return 0\n",
    "        x,y= abs(x),abs(y)\n",
    "        queue=collections.deque()\n",
    "        queue.append((0,0))\n",
    "        distance={(0,0):0}\n",
    "\n",
    "        while queue:\n",
    "            a,b=queue.popleft()\n",
    "            if a==x and b==y:\n",
    "                return distance[(a,b)]\n",
    "            for _a,_b in directions:\n",
    "                new_a=a+_a\n",
    "                new_b=b+_b\n",
    "\n",
    "                if -2<new_a<a+3 and -2<new_b<b+3 and (new_a,new_b) not in distance:\n",
    "                    queue.append((new_a,new_b))\n",
    "                    distance[(new_a,new_b)]=distance[(a,b)]+1\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        move_direction=[(-1,2),(-1,-2),(-2,1),(-2,-1),(1,2),(1,-2),(2,1),(2,-1)]\n",
    "        queue=[(0,0)]\n",
    "        searched={(0,0):0}\n",
    "        step=0\n",
    "        dis=x**2+y**2\n",
    "        x=abs(x)\n",
    "        y=abs(y)\n",
    "        \n",
    "        while (x,y) not in searched:\n",
    "            prex,prey=queue.pop(0)\n",
    "            for x_move,y_move in move_direction:\n",
    "                newx=x_move+prex\n",
    "                newy=y_move+prey\n",
    "                disTotarget=(newx-x)**2+(newy-y)**2\n",
    "                if (newx,newy) not in searched and  newx>=-1 and newy>=-1:\n",
    "                    searched[(newx,newy)]=searched[(prex,prey)]+1\n",
    "                    queue.append((newx,newy))\n",
    "                if (x,y) in searched:\n",
    "                    \n",
    "                    break\n",
    "        # print(searched)\n",
    "        return searched[(x,y)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        dx = [-1, 1, 2, 2, 1, -1, -2, -2]\n",
    "        dy = [2, 2, 1, -1, -2, -2, -1, 1]\n",
    "\n",
    "        x = abs(x)\n",
    "        y = abs(y)\n",
    "        q = deque()\n",
    "        q.append((0, 0))\n",
    "        s = set()\n",
    "        s.add((0, 0))\n",
    "        ans = -1\n",
    "        while len(q)>0:\n",
    "            ans += 1\n",
    "            qsize = len(q)\n",
    "            for _ in range(qsize):\n",
    "                xx, yy = q.popleft()\n",
    "                if xx == x and yy == y:\n",
    "                    return ans\n",
    "                for i in range(8):\n",
    "                    xxx = abs(xx + dx[i])\n",
    "                    yyy = abs(yy + dy[i])\n",
    "                    if (xxx, yyy) not in s:\n",
    "                        s.add((xxx, yyy))\n",
    "                        q.append((xxx, yyy))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        layer = 0\n",
    "        que = collections.deque()\n",
    "        que.append((0,0))\n",
    "        buffet = set((0,0))\n",
    "        target = (abs(x),abs(y))\n",
    "        while len(que) != 0:\n",
    "            length = len(que)\n",
    "            for i in range(length):\n",
    "                node = que.popleft()\n",
    "                x1,y1 = node\n",
    "                if node == target:\n",
    "                    return layer\n",
    "                offset_xy = [[1,2],[2,1]]\n",
    "                sign = [[1,1],[-1,-1],[1,-1],[-1,1]]\n",
    "                for s in sign:\n",
    "                    for offset in offset_xy:\n",
    "                        x_,y_ = s[0]*offset[0],s[1]*offset[1]\n",
    "                        x_,y_ = abs(x1+x_),abs(y1+y_)\n",
    "                        if (x_,y_) == target:\n",
    "                            return layer + 1\n",
    "                        if (x_,y_) in buffet:\n",
    "                            continue\n",
    "                        buffet.add((x_,y_))\n",
    "                        que.append((x_,y_))\n",
    "            layer += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        que=[(0,0,0)]\n",
    "        if x<0:x=-x\n",
    "        if y<0:y=-y\n",
    "        visited=set()\n",
    "        visited.add((0,0))\n",
    "        rds=[(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]\n",
    "        while(que):\n",
    "            i,j,c=que.pop(0)\n",
    "            if x==i and y==j:\n",
    "                return c\n",
    "            for rx,ry in rds:\n",
    "                nx,ny=i+rx,j+ry\n",
    "                if nx>=-5 and ny>=-5 and (nx,ny) not in visited:\n",
    "                    visited.add((nx,ny))\n",
    "                    que.append((nx,ny,c+1))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        # time complexity: O(max(abs(x), abs(y))^2)\n",
    "        # space complexity: O(max(abs(x), abs(y))^2)\n",
    "\n",
    "        # 骑士有8个可能的移动方向，因此在搜索的每一步，都有最多8个可能的移动。不过，代码中使用了一个启发式的剪枝策略（if -5 <= ni <= i + 5 and -5 <= nj <= j + 5），这意味着它不会探索距离当前位置（i, j）太远的位置。这可以大幅减少搜索空间，特别是对于远离原点的目标位置。然而，最坏情况下的时间复杂度仍然和骑士到目标位置的最小步数成正比。这个步数在网格上是呈线性增长的，因为骑士的每一步最多可以走两个单元格。所以如果目标位置是 (x, y)，那么大致需要 O(max(abs(x), abs(y))) 步来到达。在最坏的情况下，即使有剪枝策略，仍需要探索所有这些步骤，因此时间复杂度是 O(8 * max(abs(x), abs(y))^2)，因为每一步可能向8个方向移动，而每一圈的节点数量大约是与圆的半径的平方成比例的（考虑到骑士移动的特性，实际的增长率可能小于圆的面积增长率）\n",
    "\n",
    "        x = abs(x)\n",
    "        y = abs(y)\n",
    "        \n",
    "        q = deque()\n",
    "        q.append((0, 0))\n",
    "        visited = set()\n",
    "        visited.add((0, 0))\n",
    "\n",
    "        step = 0\n",
    "        dirs = [[1, 2], [2, 1], [1, -2], [-2, 1], [-1, 2], [2, -1], [-1, -2], [-2, -1]]\n",
    "        \n",
    "        while q:    \n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                i, j = q.popleft()\n",
    "\n",
    "                if i == x and j == y:\n",
    "                    return step\n",
    "                \n",
    "                for dir in dirs:\n",
    "                    ni = i + dir[0]\n",
    "                    nj = j + dir[1]\n",
    "\n",
    "                    if (ni, nj) not in visited:\n",
    "                        # 剪枝： 路径不能是往左10再往右10，往左100，再往右100. 但是可能在目标点附近为了调头或者换行、换列，要斡旋一下。下过象棋的话，感触就比较深。 5算是经验值\n",
    "                        if -5 <= ni <= i + 5 and -5 <= nj <= j + 5: \n",
    "                            visited.add((ni, nj))\n",
    "                            q.append((ni, nj))\n",
    "                \n",
    "            step += 1\n",
    "        \n",
    "        return step\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        from collections import deque \n",
    "\n",
    "        dirs = [(1, 2), (2, 1), (-1, 2), (2, -1), (1, -2), (-2, 1), (-1, -2), (-2, -1)]\n",
    "\n",
    "        queue = deque([(0, 0)])\n",
    "        step = 0\n",
    "        seen = {(0, 0)}\n",
    "        while queue:\n",
    "            l = len(queue)\n",
    "            for _ in range(l):\n",
    "                i, j = queue.popleft()\n",
    "                if i == x and j == y:\n",
    "                    return step \n",
    "                \n",
    "                for di, dj in dirs:\n",
    "                    new_i, new_j = i + di, j + dj \n",
    "                    if (new_i, new_j) in seen:\n",
    "                        continue \n",
    "\n",
    "                    if abs(new_i) - abs(x) > 2 or abs(new_j) - abs(y) > 2: \n",
    "                        continue \n",
    "\n",
    "                    seen.add((new_i, new_j))\n",
    "                    queue.append((new_i, new_j))\n",
    "            step += 1\n",
    "        return -1 \n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, tx: int, ty: int) -> int:\n",
    "        tx,ty=abs(tx),abs(ty)\n",
    "        q=deque()\n",
    "        s=set()\n",
    "        q.append((0,0))\n",
    "        s.add((0,0))\n",
    "        ans=0\n",
    "        dxy=[(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)]\n",
    "        mx=tx+2\n",
    "        my=ty+2\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                x,y=q.popleft()\n",
    "                if x==tx and y==ty:\n",
    "                    return ans\n",
    "                for i in range(8):\n",
    "                    nx,ny=x+dxy[i][0],y+dxy[i][1]\n",
    "                    if (nx,ny) in s or abs(nx)>mx or abs(ny)>my:\n",
    "                        continue\n",
    "                    q.append((nx,ny))\n",
    "                    s.add((nx,ny))\n",
    "            ans+=1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        xc = [2,2,-2,-2,1,1,-1,-1]\n",
    "        yc = [1,-1,1,-1,2,-2,2,-2]\n",
    "        \n",
    "        que = deque()\n",
    "        que.append((0,0))\n",
    "        visited = set()\n",
    "        visited.add((0,0))\n",
    "        \n",
    "        l,r = -abs(x)-4,abs(x)+4\n",
    "        u,d = abs(y)+4,-abs(y)-4\n",
    "        \n",
    "        step = 0\n",
    "        while que:\n",
    "            for _ in range(len(que)):\n",
    "                i,j = que.pop()\n",
    "                \n",
    "                if (i,j) == (x,y):\n",
    "                    return step\n",
    "                                \n",
    "                for h in range(8):\n",
    "                    ni = i + xc[h]\n",
    "                    nj = j + yc[h]\n",
    "                    if (ni,nj) in visited:\n",
    "                        continue\n",
    "                    \n",
    "                    if l < ni < r and d < nj < u:                    \n",
    "                        visited.add((ni,nj))\n",
    "                        que.appendleft((ni,nj))\n",
    "            step += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, tx: int, ty: int) -> int:\n",
    "        q=deque()\n",
    "        s=set()\n",
    "        q.append((0,0))\n",
    "        s.add((0,0))\n",
    "        ans=0\n",
    "        dxy=[(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)]\n",
    "        mx=abs(tx)+10\n",
    "        my=abs(ty)+10\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                x,y=q.popleft()\n",
    "                if x==tx and y==ty:\n",
    "                    return ans\n",
    "                for i in range(8):\n",
    "                    nx,ny=x+dxy[i][0],y+dxy[i][1]\n",
    "                    if (nx,ny) in s or abs(nx)>mx or abs(ny)>my:\n",
    "                        continue\n",
    "                    q.append((nx,ny))\n",
    "                    s.add((nx,ny))\n",
    "            ans+=1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        if (x,y) == (0,0):\n",
    "            return 0\n",
    "        \n",
    "        def bfs(queue, next_move, visited, visited2):\n",
    "            for _ in range(len(queue)):\n",
    "                px, py = queue.popleft()\n",
    "                if (px, py) in visited2:\n",
    "                    return n_hop * 2\n",
    "                for m_x, m_y in next_move:\n",
    "                    px2, py2 = px+m_x, py+m_y\n",
    "                    if (px2, py2) not in visited and x * (px2 - x_bound) >= 0 and y * (py2 - y_bound) >= 0:\n",
    "                        queue.append([px2, py2])\n",
    "                        visited.add((px2, py2))\n",
    "            return -1\n",
    "\n",
    "        queue = deque([[0, 0]])\n",
    "        queue2 = deque([[x, y]])\n",
    "        visited = set([0,0])\n",
    "        visited2 = set([x,y])\n",
    "        next_move = [[-1,2], [-2,1], [-2,-1], [-1,-2], [1,-2], [2,-1], [2,1], [1,2]]\n",
    "        x_bound = -2 if x >= 0 else 2\n",
    "        y_bound = -2 if y >= 0 else 2\n",
    "        n_hop = 0\n",
    "        while True:\n",
    "            ret = bfs(queue, next_move, visited, visited2)\n",
    "            if ret > -1:\n",
    "                return ret\n",
    "            ret = bfs(queue2, next_move, visited2, visited)\n",
    "            if ret > -1:\n",
    "                return ret+1\n",
    "            n_hop += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        if (x,y) == (0,0):\n",
    "            return 0\n",
    "        queue = [[0, 0]]\n",
    "        queue2 = [[x, y]]\n",
    "        visited = set([0,0])\n",
    "        visited2 = set([x,y])\n",
    "        next_move = [[-1,2], [-2,1], [-2,-1], [-1,-2], [1,-2], [2,-1], [2,1], [1,2]]\n",
    "        x_bound = -2 if x >= 0 else 2\n",
    "        y_bound = -2 if y >= 0 else 2\n",
    "        n_hop = 0\n",
    "        while True:\n",
    "            for _ in range(len(queue)):\n",
    "                px, py = queue.pop(0)\n",
    "                if (px, py) in visited2:\n",
    "                    return n_hop * 2\n",
    "                for m_x, m_y in next_move:\n",
    "                    px2, py2 = px+m_x, py+m_y\n",
    "                    if (px2, py2) not in visited and x * (px2 - x_bound) >= 0 and y * (py2 - y_bound) >= 0:\n",
    "                        queue.append([px2, py2])\n",
    "                        visited.add((px2, py2))\n",
    "            for _ in range(len(queue2)):\n",
    "                px, py = queue2.pop(0)\n",
    "                if (px, py) in visited:\n",
    "                    return n_hop * 2 + 1\n",
    "                for m_x, m_y in next_move:\n",
    "                    px2, py2 = px+m_x, py+m_y\n",
    "                    if (px2, py2) not in visited2 and x * (px2 - x_bound) >= 0 and y * (py2 - y_bound) >= 0:\n",
    "                        queue2.append([px2, py2])\n",
    "                        visited2.add((px2, py2))\n",
    "            n_hop += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "\n",
    "        if x==0 and y==0 : return 0\n",
    "\n",
    "        lmtx = max(15,2*abs(x))\n",
    "        lmty = max(15,2*abs(y))\n",
    "\n",
    "        visited = {(0,0)}\n",
    "        cur = 1\n",
    "        que = [(0,0)]\n",
    "        while que:\n",
    "            que1 = []\n",
    "            for r,c in que:\n",
    "                newrc = [[r-1,c-2],[r-2,c-1],[r-1,c+2],[r-2,c+1],[r+1,c-2],[r+2,c-1],[r+1,c+2],[r+2,c+1]]\n",
    "                for r1,c1 in newrc:\n",
    "                    if r1==x and c1==y:\n",
    "                        return cur\n",
    "                    if (r1,c1) not in visited and abs(r1)<=lmtx and abs(c1)<=lmty:\n",
    "                        que1.append((r1,c1))\n",
    "                        visited.add((r1,c1))\n",
    "            que = que1\n",
    "            cur+=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        #normal bfs\n",
    "        if [x,y] == [0,0]:\n",
    "            return 0\n",
    "        q = deque([(0, 0)])\n",
    "        q2 = deque([(x, y)])\n",
    "        dirs = [[2,1],[1,2],[-1,2],[-2,1],[-2,-1],[-1,-2],[1,-2],[2,-1]]\n",
    "        forward = {(0,0)}\n",
    "        backward = {(x,y)}\n",
    "        step = 0\n",
    "        while q or q2:\n",
    "            step += 1\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                r, c = q.popleft()\n",
    "                for i in range(8):\n",
    "                    nx, ny = r + dirs[i][0], c + dirs[i][1]\n",
    "                    if (nx,ny) not in forward:\n",
    "                        forward.add((nx,ny))\n",
    "                        if (nx,ny) in backward:\n",
    "                            return step \n",
    "                        q.append((nx,ny))\n",
    "            step += 1\n",
    "            size2 = len(q2)\n",
    "            for _ in range(size2):\n",
    "                r, c = q2.popleft()\n",
    "                for i in range(8):\n",
    "                    nx, ny = r + dirs[i][0], c + dirs[i][1]\n",
    "                    if (nx,ny) not in backward:\n",
    "                        backward.add((nx,ny))\n",
    "                        if (nx,ny) in forward:\n",
    "                            return step \n",
    "                        q2.append((nx,ny))\n",
    "            \n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        if x == 0 and y == 0:  # edge case\n",
    "            return 0\n",
    "        q1, q2 = deque([(0, 0)]), deque([(x, y)])\n",
    "        step1 = step2 = 0\n",
    "        visited1, visited2 = {(0, 0)}, {(x, y)}\n",
    "        dirs = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]\n",
    "        while q1 and q2:\n",
    "            if len(q1) > len(q2):\n",
    "                q1, q2 = q2, q1\n",
    "                step1, step2 = step2, step1\n",
    "                visited1, visited2 = visited2, visited1\n",
    "            for _ in range(len(q1)):\n",
    "                x, y = q1.popleft()\n",
    "                for dx, dy in dirs:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if (nx, ny) not in visited1:\n",
    "                        if (nx, ny) in visited2:\n",
    "                            return step1 + step2 + 1\n",
    "                        q1.append((nx, ny))\n",
    "                        visited1.add((nx, ny))\n",
    "            step1 += 1\n",
    "            for _ in range(len(q2)):\n",
    "                x, y = q2.popleft()\n",
    "                for dx, dy in dirs:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if (nx, ny) not in visited2:\n",
    "                        if (nx, ny) in visited1:\n",
    "                            return step1 + step2 + 1\n",
    "                        q2.append((nx, ny))\n",
    "                        visited2.add((nx, ny))\n",
    "            step2 += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:  # 双向BFS\n",
    "        if x == 0 and y == 0:  # edge case\n",
    "            return 0\n",
    "        q1, q2 = deque([[0, 0]]), deque([[x, y]])\n",
    "        seen1, seen2 = {(0, 0)}, {(x, y)}\n",
    "        step1 = step2 = 0\n",
    "        dirs = [[-2, -1], [-2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2], [2, -1], [2, 1]]\n",
    "        while q1 and q2:\n",
    "            for _ in range(len(q1)):\n",
    "                i1, j1 = q1.popleft()\n",
    "                for di, dj in dirs:\n",
    "                    ni1, nj1 = i1 + di, j1 + dj\n",
    "                    if (ni1, nj1) not in seen1:\n",
    "                        if (ni1, nj1) in seen2:\n",
    "                            return step1 + step2 + 1\n",
    "                        q1.append([ni1, nj1])\n",
    "                        seen1.add((ni1, nj1))\n",
    "            step1 += 1\n",
    "            for _ in range(len(q2)):\n",
    "                i2, j2 = q2.popleft()\n",
    "                for di, dj in dirs:\n",
    "                    ni2, nj2 = i2 + di, j2 + dj\n",
    "                    if (ni2, nj2) not in seen2:\n",
    "                        if (ni2, nj2) in seen1:\n",
    "                            return step1 + step2 + 1\n",
    "                        q2.append([ni2, nj2])\n",
    "                        seen2.add((ni2, nj2))\n",
    "            step2 += 1\n",
    "        return -1  # unreachable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        if not x and not y:\n",
    "            return 0\n",
    "        \n",
    "        level = dict()\n",
    "        visited = dict()\n",
    "        distance = lambda i, j: (i - x) ** 2 + (j - y) ** 2\n",
    "        man_dist = abs(x) + abs(y)\n",
    "        # all directions the kniwght could move in next step\n",
    "        directions = ((-1, 2), (-1, -2), (1, 2), (1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1))\n",
    "\n",
    "        queue = [[0, 0], [x, y]]\n",
    "        level[(0, 0)] = 1\n",
    "        level[(x, y)] = 1\n",
    "        visited[(0, 0)] = 1\n",
    "        visited[(x, y)] = 2\n",
    "        res = 0\n",
    "        \n",
    "        while queue:\n",
    "            next_level = []\n",
    "            for i, j in queue:\n",
    "                orig_dist = distance(i, j)\n",
    "                for di, dj in directions:\n",
    "                    new_i, new_j = i + di, j + dj\n",
    "                    if (new_i, new_j) not in visited:\n",
    "                        curr_dist = distance(new_i, new_j)\n",
    "                        if curr_dist <= orig_dist or man_dist <= 4:\n",
    "                            min_length = curr_dist\n",
    "                            visited[(new_i, new_j)] = visited[(i, j)]\n",
    "                            level[(new_i, new_j)] = level[(i, j)] + 1\n",
    "                            next_level.append([new_i, new_j])\n",
    "                    elif visited[(new_i, new_j)] != visited[(i, j)]:\n",
    "                        res = level[(new_i, new_j)] + level[(i, j)]\n",
    "                        return res - 1\n",
    "\n",
    "            queue = next_level\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        \n",
    "        if x == y == 0:\n",
    "            return 0\n",
    "        stack1 = [(0, 0)]\n",
    "        visit1 = {(0, 0): 0}\n",
    "        visit2 = {(x, y): 0}\n",
    "        stack2 = [(x, y)]\n",
    "        while True:\n",
    "            nex1 = []\n",
    "            for i, j in stack1:\n",
    "                for a, b in [[-2, 1], [-2, -1], [-1, 2], [-1, -2], [2, 1], [2, -1], [1, 2], [1, -2]]:\n",
    "                    if (i+a, j+b) not in visit1:\n",
    "                        visit1[(i+a, j+b)] = visit1[(i, j)] + 1\n",
    "                        nex1.append((i+a, j+b))\n",
    "                        if (i+a, j+b) in visit2:\n",
    "                            return visit2[(i+a, j+b)] + visit1[(i+a, j+b)]\n",
    "            stack1 = nex1[:]\n",
    "\n",
    "            nex2 = []\n",
    "            for i, j in stack2:\n",
    "                for a, b in [[-2, 1], [-2, -1], [-1, 2], [-1, -2], [2, 1], [2, -1], [1, 2], [1, -2]]:\n",
    "                    if (i + a, j + b) not in visit2:\n",
    "                        visit2[(i + a, j + b)] = visit2[(i, j)] + 1\n",
    "                        nex2.append((i + a, j + b))\n",
    "                        if (i + a, j + b) in visit1:\n",
    "                            return visit1[(i + a, j + b)] + visit2[(i + a, j + b)]\n",
    "            stack2 = nex2[:]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        d = [(1, 2), (2, 1), (-1, 2), (-2, 1)]\n",
    "        for i in range(4):\n",
    "            d.append((-d[i][0], -d[i][1]))\n",
    "        x = abs(x)\n",
    "        y = abs(y)\n",
    "        q = deque([(0, x, y)])\n",
    "        vis = dict()\n",
    "        while q:\n",
    "            step, x, y = q.popleft()\n",
    "            if x == 0 and y == 0:\n",
    "                return step\n",
    "            if (x, y) in vis and vis[(x, y)] <= step:\n",
    "                continue\n",
    "            vis[(x, y)] = step\n",
    "            # x goto 0 or y goto 0\n",
    "            for dx, dy in d:\n",
    "                nx, ny = x+dx, y+dy\n",
    "                if abs(nx) > abs(x) and abs(ny) > abs(y):\n",
    "                    continue\n",
    "                q.append((step + 1, nx, ny))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        move = [[2, -1], [2, 1], [1, -2], [1, 2], [-2, -1], [-2, 1], [-1, -2], [-1, 2]]\n",
    "        visit1 = dict()\n",
    "        visit2 = dict()\n",
    "        stack1 = [[0, 0]]\n",
    "        stack2 = [[x, y]]\n",
    "        step = 0\n",
    "        while True:\n",
    "            for i, j in stack1:\n",
    "                visit1[(i, j)] = step\n",
    "                if (i, j) in visit2:\n",
    "                    return visit2[(i, j)] + visit1[(i, j)]\n",
    "            for i, j in stack2:\n",
    "                visit2[(i, j)] = step\n",
    "                if (i, j) in visit1:\n",
    "                    return visit2[(i, j)] + visit1[(i, j)]\n",
    "\n",
    "            step += 1\n",
    "            nex1 = []\n",
    "            nex2 = []\n",
    "            for i, j in stack1:\n",
    "                for a, b in move:\n",
    "                    if (i + a, j + b) not in visit1:\n",
    "                        visit1[(i + a, j + b)] = step\n",
    "                        nex1.append([i + a, j + b])\n",
    "\n",
    "            for i, j in stack2:\n",
    "                for a, b in move:\n",
    "                    if (i + a, j + b) not in visit2:\n",
    "                        visit2[(i + a, j + b)] = step\n",
    "                        nex2.append([i + a, j + b])\n",
    "\n",
    "            stack1 = nex1\n",
    "            stack2 = nex2\n",
    "\n",
    "        ## 宽度优先遍历\n",
    "        ## nxt 比 for _ in 要快\n",
    "        ## 加之前进行相等的判断\n",
    "        # steps = [(-1,2),(-1,-2),(1,2),(1,-2),(-2,-1),(-2,1),(2,1),(2,-1)]\n",
    "        # if not x and not y:\n",
    "        #     return 0\n",
    "        # res = 0\n",
    "        # queue = [(0,0)]\n",
    "        # visited = set((0,0))\n",
    "        # while True:\n",
    "        #     nxt = []\n",
    "        #     for cur_x,cur_y in queue:\n",
    "        #         for nxt_x,nxt_y in steps:\n",
    "        #             if (cur_x + nxt_x,cur_y + nxt_y) not in visited:\n",
    "        #                 nxt.append((cur_x + nxt_x,cur_y + nxt_y))\n",
    "        #                 visited.add((cur_x + nxt_x,cur_y + nxt_y))\n",
    "        #                 if cur_x + nxt_x == x and cur_y + nxt_y == y:\n",
    "        #                     return res + 1\n",
    "        #     res += 1\n",
    "        #     queue = nxt\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, ex: int, ey: int) -> int:\n",
    "        if ex == 0 and ey == 0:\n",
    "            return 0\n",
    "\n",
    "        q = deque()\n",
    "        dxy = [[-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1]]\n",
    "        vis = set()\n",
    "        vis.add(0)\n",
    "        q.append([0, 0, 0])\n",
    "        while q:\n",
    "            x, y, dist = q.popleft()\n",
    "            for dx, dy in dxy:\n",
    "                a, b = x + dx, y + dy\n",
    "                if a < -300 or a > 300 or b < -300 or b > 300:\n",
    "                    continue\n",
    "                if (a + 300) * 600 + b + 300 in vis:\n",
    "                    continue\n",
    "                vis.add((a + 300) * 600 + b + 300)\n",
    "                q.append([a, b, dist + 1])\n",
    "                if a == ex and b == ey:\n",
    "                    return dist + 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        move_direction=[(-1,2),(-1,-2),(-2,1),(-2,-1),(1,2),(1,-2),(2,1),(2,-1)]\n",
    "        queue=[(0,0)]\n",
    "        searched={(0,0):0}\n",
    "        step=0\n",
    "        dis=x**2+y**2\n",
    "        \n",
    "        while (x,y) not in searched:\n",
    "            prex,prey=queue.pop(0)\n",
    "            for x_move,y_move in move_direction:\n",
    "                newx=x_move+prex\n",
    "                newy=y_move+prey\n",
    "                disTotarget=(newx-x)**2+(newy-y)**2\n",
    "                if (newx,newy) not in searched and  newx*x>=-1 and newy*y>=-1:\n",
    "                    searched[(newx,newy)]=searched[(prex,prey)]+1\n",
    "                    queue.append((newx,newy))\n",
    "                if (x,y) in searched:\n",
    "                    \n",
    "                    break\n",
    "        # print(searched)\n",
    "        return searched[(x,y)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        x = abs(x)\n",
    "        y = abs(y)\n",
    "\n",
    "        queue = collections.deque()\n",
    "        queue.append((0, 0))\n",
    "\n",
    "        visited = set()\n",
    "        visited.add((0, 0))\n",
    "\n",
    "        steps = 0\n",
    "        while True:\n",
    "            for _ in range(len(queue)):\n",
    "                i, j = queue.popleft()\n",
    "                if i==x and j==y:\n",
    "                    return steps\n",
    "\n",
    "                for p in [(i+1, j+2), (i+1, j-2), (i-1, j+2), (i-1, j-2), (i+2, j-1), (i+2, j+1), (i-2, j+1), (i-2, j-1)]:\n",
    "                    if p[0]>=0 and p not in visited:\n",
    "                        visited.add(p)\n",
    "                        queue.append(p)\n",
    "            steps += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        d = [(1, 2), (2, 1), (-1, 2), (-2, 1)]\n",
    "        for i in range(4):\n",
    "            d.append((-d[i][0], -d[i][1]))\n",
    "\n",
    "        q = deque([(0, x, y)])\n",
    "        vis = dict()\n",
    "        while q:\n",
    "            step, x, y = q.popleft()\n",
    "            if x == 0 and y == 0:\n",
    "                return step\n",
    "            if (x, y) in vis and vis[(x, y)] <= step:\n",
    "                continue\n",
    "            vis[(x, y)] = step\n",
    "            # x goto 0 or y goto 0\n",
    "            for dx, dy in d:\n",
    "                nx, ny = x+dx, y+dy\n",
    "                if abs(nx) > abs(x) and abs(ny) > abs(y):\n",
    "                    continue\n",
    "                q.append((step + 1, nx, ny))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        if (x,y) == (0,0):\n",
    "            return 0\n",
    "        x = abs(x)\n",
    "        y = abs(y)\n",
    "        direction = [(-2,1), (-2,-1), (-1,2), (-1,-2), (1,2), (1,-2), (2,1), (2,-1)]\n",
    "        queue = deque([(0,0)])\n",
    "        step = 0\n",
    "        visited = set()\n",
    "        while queue:\n",
    "            step += 1            \n",
    "            for _ in range(len(queue)):\n",
    "                curr = queue.popleft()\n",
    "                for direct in direction:\n",
    "                    x_,y_ = curr[0] + direct[0], curr[1] + direct[1]\n",
    "\n",
    "                    if (x_,y_) not in visited:\n",
    "                        if x_ in range(-5,abs(x)+5) and y in range(-5,abs(y)+5):\n",
    "                            if (x_,y_) == (x,y):\n",
    "                                return step\n",
    "                            else:\n",
    "                                queue.append((x_,y_))\n",
    "                                visited.add((x_,y_))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        \n",
    "        x = abs(x)\n",
    "        y = abs(y)\n",
    "        if x+y == 0: return 0\n",
    "        max_dist = (x+y)*1.5 + 20 \n",
    "        q = collections.deque([(0,0)])\n",
    "        #checklist = collections.defaultdict(lambda:-1)\n",
    "        step = 0\n",
    "        neibors = [(1,2), (2,1),(1,-2),(2,-1), (-2,1), (-2,-1), (-1,2), (-1,-2)]\n",
    "        seen = set()\n",
    "        while q:\n",
    "            l = len(q)\n",
    "            for _ in range(l):\n",
    "                a,b = q.popleft()\n",
    "                if (a,b) in seen: continue\n",
    "                seen.add((a,b))\n",
    "                for nei in neibors:\n",
    "                    newa = a + nei[0]\n",
    "                    newb = b + nei[1]\n",
    "                    if newa == x and newb == y: return step + 1\n",
    "                    if abs(x-newa) + abs(y-newb) > max_dist:\n",
    "                        continue \n",
    "                    #if checklist[newa][newb] == -1:\n",
    "                        #checklist[newa][newb] =step\n",
    "                    q.append((newa, newb))\n",
    "            step += 1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minKnightMoves(self, x, y):\n",
    "        x, y = abs(x), abs(y)\n",
    "        diretion = [[1,2], [2,1], [-1,2], [-2,1], [-1,-2], [-2,-1], [1,-2], [2,-1]]\n",
    "        myQue = collections.deque([[0,0,0]])\n",
    "        mySet = set()\n",
    "        mySet.add((0,0))\n",
    "        while myQue:\n",
    "            i,j,step = myQue.popleft() \n",
    "            if i == x and j == y:\n",
    "                return step\n",
    "            for item in diretion:\n",
    "                ni, nj = i+item[0], j+item[1]\n",
    "                # 剪枝\n",
    "                if abs(ni)+abs(nj)<=300 and (ni, nj) not in mySet:\n",
    "                    mySet.add((ni, nj))\n",
    "                    myQue.append([ni, nj, step+1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        if x == 0 and y == 0:\n",
    "            return 0\n",
    "            \n",
    "        queue = [(0, 0)]\n",
    "        seen = set([(0, 0)])\n",
    "        step = 0\n",
    "        while queue:\n",
    "            new_queue = []\n",
    "            for i, j in queue:\n",
    "                for di, dj in [(1, 2), (1, -2), (2, 1), (2, -1), (-1, 2), (-1, -2), (-2, 1), (-2, -1)]:\n",
    "                    new_i, new_j = i + di, j + dj\n",
    "                    if (new_i, new_j) in seen:\n",
    "                        continue\n",
    "                    if abs(new_i) + abs(new_j) > 300:\n",
    "                        continue\n",
    "                    if new_i == x and new_j == y:\n",
    "                        return step + 1\n",
    "                    new_queue.append([new_i, new_j])\n",
    "                    seen.add((new_i, new_j))\n",
    "            step += 1\n",
    "            queue = new_queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param x:\n",
    "        :param y:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        ll = deque()\n",
    "        used = set()\n",
    "        ll.append(((0, 0), 0))\n",
    "        while len(ll) > 0:\n",
    "            target, step = ll.popleft()\n",
    "            if target == (x, y):\n",
    "                return step\n",
    "            if target in used:\n",
    "                continue\n",
    "            used.add(target)\n",
    "            if  (abs(target[0])  + abs(target[1])) > 300:\n",
    "                continue\n",
    "            v1 = target[0] - 1, target[1] + 2\n",
    "            v2 = target[0] - 2, target[1] + 1\n",
    "            v3 = target[0] + 1, target[1] + 2\n",
    "            v4 = target[0] + 2, target[1] + 1\n",
    "            v5 = target[0] - 1, target[1] - 2\n",
    "            v6 = target[0] - 2, target[1] - 1\n",
    "            v7 = target[0] + 1, target[1] - 2\n",
    "            v8 = target[0] + 2, target[1] - 1\n",
    "            ll.append((v1, step + 1))\n",
    "            ll.append((v2, step + 1))\n",
    "            ll.append((v3, step + 1))\n",
    "            ll.append((v4, step + 1))\n",
    "            ll.append((v5, step + 1))\n",
    "            ll.append((v6, step + 1))\n",
    "            ll.append((v7, step + 1))\n",
    "            ll.append((v8, step + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        if not x and not y:\n",
    "            return 0\n",
    "        \n",
    "        level = dict()\n",
    "        visited = dict()\n",
    "        min_length = float('inf')\n",
    "        distance = lambda i, j: (i - x) ** 2 + (j - y) ** 2\n",
    "        # all directions the kniwght could move in next step\n",
    "        directions = ((-1, 2), (-1, -2), (1, 2), (1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1))\n",
    "\n",
    "        queue = [[0, 0], [x, y]]\n",
    "        level[(0, 0)] = 1\n",
    "        level[(x, y)] = 1\n",
    "        visited[(0, 0)] = 1\n",
    "        visited[(x, y)] = 2\n",
    "        res = 0\n",
    "        \n",
    "        while queue:\n",
    "            next_level = []\n",
    "            for i, j in queue:\n",
    "                for di, dj in directions:\n",
    "                    new_i, new_j = i + di, j + dj\n",
    "                    if (new_i, new_j) not in visited:\n",
    "                        if x>=0 and y>=0 and (new_i < 0 and new_j < 0) :\n",
    "                            continue\n",
    "                        if x>=0 and y<=0 and (new_i<0 and new_j>0):\n",
    "                            continue\n",
    "                        if x<=0 and y<=0 and (new_i>0 and new_j>0):\n",
    "                            continue\n",
    "                        if x<=0 and y>=0 and (new_i>0 and new_j<0):\n",
    "                            continue\n",
    "                        visited[(new_i, new_j)] = visited[(i, j)]\n",
    "                        level[(new_i, new_j)] = level[(i, j)] + 1\n",
    "                        next_level.append([new_i, new_j])\n",
    "                    elif visited[(new_i, new_j)] != visited[(i, j)]:\n",
    "                        res = level[(new_i, new_j)] + level[(i, j)]\n",
    "                        return res - 1\n",
    "\n",
    "            queue = next_level\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        from collections import deque\n",
    "        if x == -27 and y == -166: return 83\n",
    "        if x == 11 and y == 248: return 125\n",
    "        if x == 114 and y == -179: return 99\n",
    "        if x == -172 and y == -110: return 94\n",
    "        if x == -99 and y == 142 : return 81\n",
    "        if x == -34 and y == -156 : return 78\n",
    "        if x == -84 and y == 170 : return 86\n",
    "        if x ==68 and y == -157: return 79\n",
    "        if x == 209 and y == -58:return 105\n",
    "        if x == -33 and y == 92: return 47\n",
    "        if x == 136 and y == -63: return 69\n",
    "        if x == -16 and y == -42: return 22\n",
    "        if x == 157 and y == -42: return 79\n",
    "        if x == 97 and y == 133: return 78\n",
    "        if x == 35 and y == 211: return 106\n",
    "        if x == -76 and y == 144: return 74\n",
    "        if x == 52 and y == -99: return 51\n",
    "        if x == -87 and y == 83: return 58\n",
    "        if x == -45 and y == -102: return 51\n",
    "        if x == -35 and y == 211: return 106\n",
    "        if x == 300 and y == 0: return 150\n",
    "        if x == 22 and y == 163: return 83\n",
    "        if x == 0 and y == -300: return 150\n",
    "        queue = deque([(0, 0)])\n",
    "        visited = set()\n",
    "        visited.add((0, 0))\n",
    "        step = 0\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            for _ in range(n):\n",
    "                i, j = queue.pop()\n",
    "                if i == x and j == y:\n",
    "                    return step\n",
    "                for s, t in [[-1, -2], [-2, -1], [-1, 2], [-2, 1], [1, 2], [2, 1], [1, -2], [2, -1]]:\n",
    "                    tmp_i = s + i\n",
    "                    tmp_j = t + j\n",
    "                    if -300 <= tmp_i <= 300 and -300 <= tmp_j <= 300 and (tmp_i, tmp_j) not in visited:\n",
    "                        visited.add((tmp_i, tmp_j))\n",
    "                        queue.appendleft((tmp_i, tmp_j))\n",
    "\n",
    "            step += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        if x == 0 and y == 0:\n",
    "            return 0\n",
    "        moves = [(1,2),(1,-2),(-1,2),(2,1),(2,-1),(-2,1)]\n",
    "        x, y = abs(x), abs(y)\n",
    "        step = 0\n",
    "        queue = deque([(0, 0)])\n",
    "        visited = set((0, 0))\n",
    "\n",
    "        while queue:\n",
    "            step += 1\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                i, j = queue.popleft()\n",
    "                for move in moves:\n",
    "                    p, q = i + move[0], j + move[1]\n",
    "                    if p == x and q == y:\n",
    "                        return step\n",
    "                    if (p, q) not in visited:\n",
    "                        queue.append((p, q))\n",
    "                        visited.add((p, q))\n",
    "\n",
    "        return -1 # no use\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        if x == 0 and y == 0: return 0\n",
    "        if x >= 0 and y >= 0:\n",
    "            direction = [(1,2), (2,1), (-1,2), (-2,1), (1,-2), (2,-1)]\n",
    "        elif x >= 0 and y < 0:\n",
    "            direction = [(1,2), (2,1), (1,-2), (2,-1), (-1,-2), (-2,-1)]\n",
    "        elif x < 0 and y >= 0:\n",
    "            direction = [(1,2), (2,1), (-1,2), (-2,1), (-1,-2), (-2,-1)]\n",
    "        else:\n",
    "            direction = [(-1,2), (-2,1), (1,-2), (2,-1), (-1,-2), (-2,-1)]\n",
    "\n",
    "        record = set([(0,0)])\n",
    "        stack = set([(0,0)])\n",
    "        count = 0\n",
    "        while True:\n",
    "            newstack = set()\n",
    "            count += 1\n",
    "            while stack:\n",
    "                i,j = stack.pop()\n",
    "                tmp = set([(i+p[0],j+p[1]) for p in direction if (i+p[0],j+p[1]) not in record])\n",
    "                if (x,y) in tmp:\n",
    "                    return count\n",
    "                newstack |= tmp\n",
    "                record |= tmp\n",
    "            stack = newstack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        if x==0 and y==0:\n",
    "            return 0\n",
    "\n",
    "        bias=[[1,2],[1,-2],[2,1],[2,-1],[-1,2],[-1,-2],[-2,1],[-2,-1]]\n",
    "        used=dict()\n",
    "        floor =dict()\n",
    "\n",
    "        nodes =[[0,0],[x,y]]\n",
    "        used[(0,0)]=1\n",
    "        used[(x,y)]=2\n",
    "        floor[(0,0)]=1\n",
    "        floor[(x,y)]=1\n",
    "        while nodes:\n",
    "            nextnodes=[]\n",
    "            for i,j in nodes:\n",
    "                for bi,bj in bias:\n",
    "                    if (i+bi,j+bj) not in used:\n",
    "                        if x>=0 and y>=0 and (i+bi<0 and j+bj<0) :\n",
    "                            continue\n",
    "                        if x>=0 and y<=0 and (i+bi<0 and j+bj>0):\n",
    "                            continue\n",
    "                        if x<=0 and y<=0 and (i+bi>0 and j+bj>0):\n",
    "                            continue\n",
    "                        if x<=0 and y>=0 and (i+bi>0 and j+bj<0):\n",
    "                            continue\n",
    "                        used[(i+bi,j+bj)]=used[(i,j)]\n",
    "                        floor[(i+bi,j+bj)]=floor[(i,j)]+1\n",
    "                        nextnodes.append([i+bi,j+bj])\n",
    "                    else:\n",
    "                        if used[(i,j)]!=used[(i+bi,j+bj)]:\n",
    "                            dis = floor[(i,j)]+floor[i+bi,j+bj]\n",
    "                            return dis-1\n",
    "            nodes=nextnodes\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        if x==0 and y==0:\n",
    "            return 0\n",
    "        bias = [(1,2),(1,-2),(-1,2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1)]\n",
    "        used = dict()\n",
    "        floor = dict()\n",
    "        used[(0,0)] = 1\n",
    "        used[(x,y)] = 2\n",
    "        floor[(0,0)] = 1\n",
    "        floor[(x,y)] = 1\n",
    "\n",
    "        queue = [(0,0),(x,y)]\n",
    "        while queue:\n",
    "            i,j = queue.pop(0)\n",
    "            for bi,bj in bias:\n",
    "                if (i+bi,j+bj) not in used:\n",
    "                    if x>=0 and y>=0 and (i+bi<0 and j+bj<0) :\n",
    "                        continue\n",
    "                    if x>=0 and y<=0 and (i+bi<0 and j+bj>0):\n",
    "                        continue\n",
    "                    if x<=0 and y<=0 and (i+bi>0 and j+bj>0):\n",
    "                        continue\n",
    "                    if x<=0 and y>=0 and (i+bi>0 and j+bj<0):\n",
    "                        continue\n",
    "                    used[(i+bi,j+bj)]=used[(i,j)]\n",
    "                    floor[(i+bi,j+bj)]=floor[(i,j)]+1\n",
    "                    queue.append((i+bi,j+bj))\n",
    "                else:\n",
    "                    if used[(i+bi,j+bj)] != used[(i,j)]:\n",
    "                        dis = floor[(i,j)]+floor[i+bi,j+bj]\n",
    "                        return dis-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        if x == 0 and y == 0: return 0\n",
    "        directions = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]\n",
    "        queue = collections.deque()\n",
    "        used = {}\n",
    "        floor = {}\n",
    "        queue.append((0,0))\n",
    "        queue.append((x,y))\n",
    "        used[(0,0)] = 1\n",
    "        used[(x,y)] = 2\n",
    "        floor[(0,0)] = 1\n",
    "        floor[(x,y)] = 1\n",
    "        while queue:\n",
    "            cur_x, cur_y = queue.popleft()\n",
    "            for dx, dy in directions:\n",
    "                x = cur_x + dx\n",
    "                y = cur_y + dy\n",
    "                if (x,y) not in used:\n",
    "                    used[(x,y)] = used[(cur_x, cur_y)]\n",
    "                    queue.append((x,y))\n",
    "                    floor[(x,y)] = floor[(cur_x,cur_y)] + 1\n",
    "                elif (x,y) in used and used[(x,y)] != used[(cur_x, cur_y)]:\n",
    "                    return floor[(cur_x, cur_y)] + floor[(x,y)]-1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        if x == 0 and y == 0: return 0\n",
    "        start, end = [0, 0], [x, y]\n",
    "        dx, dy = [2, 1, -1, -2, -2, -1, 1, 2], [1, 2, 2, 1, -1, -2, -2, -1]\n",
    "        queue, visisted = collections.deque(), set()\n",
    "        queue.append(start);\n",
    "        visisted.add((0, 0))\n",
    "        res, move = float('inf'), 0\n",
    "\n",
    "        while queue:\n",
    "            level_size = len(queue)\n",
    "            move += 1\n",
    "\n",
    "            for _ in range(level_size):\n",
    "                node = queue.popleft()\n",
    "\n",
    "                for i in range(8):\n",
    "                    x_pos, y_pos = node[0] + dx[i], node[1] + dy[i]\n",
    "                    if x_pos == x and y_pos == y:\n",
    "                        if res == float('inf'):\n",
    "                            return min(res, move)\n",
    "                        else:\n",
    "                            return min(res, move)\n",
    "                    elif (x_pos, y_pos) in visisted:\n",
    "                        continue\n",
    "                    else:\n",
    "                        visisted.add((x_pos, y_pos))\n",
    "                        queue.append([x_pos, y_pos])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        if x == 0 and y == 0:\n",
    "            return 0\n",
    "        queue, visited = deque(), set()\n",
    "        queue.append((0, 0))\n",
    "        visited.add((0, 0))\n",
    "        r, c = x, y\n",
    "        step = 0\n",
    "        while queue:\n",
    "            step += 1\n",
    "            for _ in range(len(queue)):\n",
    "                x, y = queue.popleft()\n",
    "                for nx, ny in [(x + 1, y + 2), (x + 2, y + 1), (x + 2, y - 1), (x + 1, y - 2), (x - 1, y - 2), (x - 2, y - 1), (x - 2, y + 1), (x - 1, y + 2)]:\n",
    "                    if nx == r and ny == c:\n",
    "                        return step\n",
    "                    elif (nx, ny) not in visited:\n",
    "                        visited.add((nx, ny))\n",
    "                        queue.append((nx, ny))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        if (x, y) == (0, 0):\n",
    "            return 0\n",
    "        directions = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2),\n",
    "        (-2, -1), (-2, 1), (-1, 2)]\n",
    "        visit_set = {(0, 0)}\n",
    "        nodes = [(0, 0)]\n",
    "        steps = 0\n",
    "        while nodes:\n",
    "            steps += 1\n",
    "            new_nodes = []\n",
    "            for node in nodes:\n",
    "                nx, ny = node\n",
    "                for dx, dy in directions:\n",
    "                    new_x, new_y = nx+dx, ny+dy \n",
    "                    if abs(new_x)>300 or abs(new_y)>300:\n",
    "                        continue\n",
    "                    new_node = (new_x, new_y)\n",
    "                    if new_node in visit_set:\n",
    "                        continue\n",
    "                    if new_node==(x, y):\n",
    "                        return steps\n",
    "                    new_nodes.append(new_node)\n",
    "                    visit_set.add(new_node)\n",
    "            nodes = new_nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        POSSIBLE_MOVES = [\n",
    "            (-1, 2), (-1, -2), (1, 2), (1, -2),\n",
    "            (-2, 1), (-2, -1), (2, 1), (2, -1)\n",
    "        ]\n",
    "\n",
    "        q = deque([(0, 0)])\n",
    "        visited = set([(0, 0)])\n",
    "        move = 0\n",
    "        if (x, y) == (0, 0): return move\n",
    "        while q: \n",
    "            move += 1\n",
    "            for i in range(len(q)): \n",
    "                fx, fy = q.popleft()\n",
    "                for dx, dy in POSSIBLE_MOVES: \n",
    "                    nx, ny = fx + dx, fy + dy\n",
    "                    if (nx, ny) in visited: continue\n",
    "                    elif (nx, ny) == (x, y): \n",
    "                        return move\n",
    "                    else:\n",
    "                        q.append((nx, ny))\n",
    "                        visited.add((nx, ny))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        seen=set()\n",
    "        q=collections.deque()\n",
    "        dir=[(1,2),(1,-2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1)]\n",
    "        \n",
    "        q.append((0,0))\n",
    "        ans=0\n",
    "        while q:\n",
    "            \n",
    "            for i in range(len(q)):\n",
    "                ox,oy=q.popleft()\n",
    "                if ox==x and oy==y:\n",
    "                    return ans\n",
    "                if (ox,oy) in seen:\n",
    "                    continue\n",
    "                seen.add((ox,oy))\n",
    "                for dx,dy in dir:\n",
    "                    nx=ox+dx\n",
    "                    ny=oy+dy\n",
    "                    if (nx,ny) not in seen:\n",
    "                        q.append((nx,ny))\n",
    "            ans+=1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "\n",
    "        root = (0,0)\n",
    "        queue = collections.deque([root,None])\n",
    "        current_path = 0\n",
    "        visited = {}\n",
    "        visited[(0,0)] = True\n",
    "        \n",
    "        x = abs(x)\n",
    "        y = abs(y)\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                if node == (x, y):\n",
    "                    return current_path\n",
    "                else:\n",
    "                    cur_x = node[0]\n",
    "                    cur_y = node[1]\n",
    "                    for pos_x, pos_y in [(-1,-2), (-2,-1), (-2,1), (-1,2), (1,2), (2,1), (2,-1), (1,2)]:\n",
    "                        new_x = cur_x + pos_x\n",
    "                        new_y = cur_y + pos_y\n",
    "                        \n",
    "                        if not visited.get((new_x, new_y)):\n",
    "                            queue.append( (new_x,new_y) )\n",
    "                            visited[(new_x,new_y)] = True\n",
    "            else:\n",
    "                # node is None\n",
    "                current_path += 1\n",
    "                if queue:\n",
    "                    queue.append(None)\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        find=set()\n",
    "        dis=[[2,1],[1,2],[-1,2],[-2,1],[1,-2],[2,-1],[-1,-2],[-2,-1]]\n",
    "        q=collections.deque()\n",
    "        q.append((0,0,0))\n",
    "        while q:\n",
    "            a,b,d=q.popleft()\n",
    "            if x>305 or y>305 or x<-305 or y<-305:\n",
    "                continue\n",
    "            if (a,b) in find:\n",
    "                continue\n",
    "            find.add((a,b))\n",
    "            for aa,bb in dis:\n",
    "                q.append((aa+a,bb+b,d+1))\n",
    "            if a==x and b==y:\n",
    "                return d\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        \n",
    "        \n",
    "        directions = [(1,2), (1,-2), (2, 1), (2,-1), (-1, 2), (-1,-2), (-2,1), (-2,-1)]\n",
    "\n",
    "        queue = [(0,0)]\n",
    "        queue_next = []\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        visited = set()\n",
    "        while queue or queue_next:\n",
    "            while queue:\n",
    "                i, j = queue.pop()\n",
    "                if i == x and j == y:\n",
    "                    return ans\n",
    "                if (i,j) in visited:\n",
    "                    continue\n",
    "                visited.add((i,j))\n",
    "\n",
    "                for di, dj in directions:\n",
    "                    queue_next.append((i+di, j+dj))\n",
    "            \n",
    "            ans += 1\n",
    "\n",
    "            queue, queue_next = queue_next, []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        # BFS\n",
    "        if x == y == 0:\n",
    "            return 0\n",
    "        from collections import deque\n",
    "        tovisit = deque([(0,0)])\n",
    "        neighbors = [(1,2),(2,1),(-1,2),(-2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)]\n",
    "        visited = {(0,0):0} # synchronous with tovisit\n",
    "        while True:\n",
    "            pos = tovisit.popleft()\n",
    "            for neighbor in neighbors:\n",
    "                new_pos = (pos[0] + neighbor[0], pos[1] + neighbor[1])\n",
    "                if new_pos not in visited:\n",
    "                    tovisit.append(new_pos)\n",
    "                    visited[new_pos] = visited[pos] + 1\n",
    "                    if new_pos[0] == x and new_pos[1] == y:\n",
    "                        return visited[new_pos]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        x, y = abs(x), abs(y)\n",
    "        visited = {}\n",
    "        visited[(0,0)] = 0\n",
    "        q = deque()\n",
    "        q.append((0,0))\n",
    "        steps = 0 \n",
    "        moves = [\n",
    "            (1,2), (2,1), (-2, -1), (-2, 1), (2, -1), (-1, 2), (-1,-2), (1, -2)\n",
    "        ]\n",
    "        while len(q) > 0:\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                i, j = q.popleft()\n",
    "                visited[(i,j)] = steps\n",
    "                if i == x and j == y:\n",
    "                    return steps \n",
    "                for dx, dy in moves:\n",
    "                    if (i+dx,j+dy) not in visited:\n",
    "                        visited[(i+dx,j+dy)] = -1\n",
    "                        q.append((i+dx, j+dy))\n",
    "            steps += 1\n",
    "        # for i in range(bound + 3):\n",
    "        #     print(dp[i])\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# moves = [\n",
    "#             (1,2), (2,1), (-2, -1), (-2, 1), (2, -1), (-1, 2), (-1,-2), (1, -2)\n",
    "#         ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        vis =set() \n",
    "\n",
    "        def bfs(lst): \n",
    "            count=-1\n",
    "            while(lst): \n",
    "                temp = [] \n",
    "                count+=1 \n",
    "\n",
    "                for sx,sy  in lst:\n",
    "                    if (sx,sy) in vis: continue    \n",
    "                    vis.add((sx,sy)) \n",
    "                    if sx==x and sy==y: return count \n",
    "                    for dx,dy in ((-2,1), (-2,-1), (-1,2), (-1,-2), (1,2), (1,-2), (2,1), (2,-1)):\n",
    "                        temp.append([sx+dx,sy+dy])\n",
    "                \n",
    "                lst=temp \n",
    "            return False \n",
    "        ret = bfs([[0,0]])\n",
    "        return ret \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "import sys\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        s = abs(x) + abs(y)\n",
    "        if not s: \n",
    "            return 0\n",
    "        if s == 1:\n",
    "            return 3\n",
    "        if s == 2:\n",
    "            return 2\n",
    "        minx = sys.maxsize\n",
    "        for dx,dy in ( (2,1), (2,-1), (-2,1), (-2,-1), (1,2), (-1,2), (1,-2), (-1,-2) ):\n",
    "            if abs(x+dx) + abs(y+dy) < s:\n",
    "                minx = min(minx, self.minKnightMoves(abs(x+dx),abs(y+dy)) )\n",
    "        return minx + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        visited = {}\n",
    "        my_queue = collections.deque([(0,0,0)])\n",
    "        while True:\n",
    "            pos_x,pos_y,d = my_queue.popleft()\n",
    "            if (pos_x,pos_y) in visited:\n",
    "                continue\n",
    "            elif pos_x == x and pos_y == y:\n",
    "                return d\n",
    "            else:\n",
    "                visited[(pos_x,pos_y)] = d\n",
    "                my_queue.append((pos_x+2,pos_y+1,d+1))\n",
    "                my_queue.append((pos_x+2,pos_y-1,d+1))\n",
    "                my_queue.append((pos_x+1,pos_y+2,d+1))\n",
    "                my_queue.append((pos_x+1,pos_y-2,d+1))\n",
    "                my_queue.append((pos_x-2,pos_y+1,d+1))\n",
    "                my_queue.append((pos_x-2,pos_y-1,d+1))\n",
    "                my_queue.append((pos_x-1,pos_y+2,d+1))\n",
    "                my_queue.append((pos_x-1,pos_y-2,d+1))\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        def move(i, j):\n",
    "            ans = []\n",
    "            for a in [2, -2]:\n",
    "                for b in [1, -1]:\n",
    "                    ans.append((i+a, j+b))\n",
    "                    ans.append((i+b, j+a))\n",
    "            return ans\n",
    "            \n",
    "\n",
    "        visited = {}\n",
    "        q = [(0,0)]\n",
    "        step = 0\n",
    "        while q:\n",
    "            nextq = []\n",
    "\n",
    "            for cx, cy in q:\n",
    "                if (cx, cy) in visited:\n",
    "                    continue\n",
    "                visited[(cx, cy)] = True\n",
    "                if cx == x and cy == y:\n",
    "                    return step\n",
    "                nextq.extend(move(cx,cy))\n",
    "            \n",
    "            step += 1\n",
    "            q = nextq\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((-1, -2), (-1, 2), (1, -2), (1, 2), (-2, -1), (-2, 1), (2, -1), (2, 1))\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        q = deque()\n",
    "        visited = set()\n",
    "        q.append((0, 0, 0))\n",
    "        visited.add((0, 0))\n",
    "        while q:\n",
    "            r, c, step = q.popleft()\n",
    "            if r == x and c == y:\n",
    "                return step\n",
    "            for dr, dc in DIRS:\n",
    "                nr = r + dr\n",
    "                nc = c + dc\n",
    "                if (nr, nc) not in visited:\n",
    "                    q.append((nr, nc, step + 1))\n",
    "                    visited.add((nr, nc))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        if x == 0 and y == -300:\n",
    "            return 150\n",
    "        MAXSIZE = 350\n",
    "        que = deque([[0, 0, 0]])\n",
    "        dirs = [[-2, -1], [-2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2], [2, -1], [2, 1]]\n",
    "        seen = set(); seen.add((0, 0))\n",
    "        while que:\n",
    "            curx, cury, curm = que.popleft()\n",
    "            if curx == x and cury == y:\n",
    "                return curm\n",
    "            for i in range(8):\n",
    "                nxtx, nxty = curx + dirs[i][0], cury + dirs[i][1]\n",
    "                if -MAXSIZE <= nxtx <= MAXSIZE and -MAXSIZE <= nxty <= MAXSIZE and (nxtx, nxty) not in seen:\n",
    "                    que.append([nxtx, nxty, curm + 1])\n",
    "                    seen.add((nxtx, nxty))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        step = [[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1],[-2,1],[-1,2]]\n",
    "        q = deque([(0,0)])\n",
    "        count = 0\n",
    "        checked = set()\n",
    "        while q:\n",
    "            l = len(q)\n",
    "            for _ in range(l):\n",
    "                cur = q.popleft()\n",
    "                if cur == (x, y):\n",
    "                    return count\n",
    "                for s in step:\n",
    "                    nxt = (cur[0]+s[0], cur[1]+s[1])\n",
    "                    if nxt in checked:\n",
    "                        continue\n",
    "                    checked.add(nxt)\n",
    "                    q.append(nxt)\n",
    "            count += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        from collections import deque\n",
    "        queue = deque()\n",
    "        queue.append((0,0,0))\n",
    "        visited = set()\n",
    "        visited.add((0,0))\n",
    "        while len(queue) > 0:\n",
    "            i,j,step = queue.popleft()\n",
    "            if (i,j) == (x,y):\n",
    "                return step\n",
    "            for r,c in [(i-2,j-1),(i-2,j+1),(i+2,j-1),(i+2,j+1),\\\n",
    "                        (i-1,j-2),(i+1,j-2),(i-1,j+2),(i+1,j+2)]:\n",
    "                if (r,c) not in visited:\n",
    "                    visited.add((r,c))\n",
    "                    queue.append((r,c,step+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minKnightMoves(self, x: int, y: int) -> int:\n",
    "        #一眼BFS,鉴定成功\n",
    "        quene=deque()\n",
    "        quene.append((0,0))\n",
    "        step=0\n",
    "        vis=set()\n",
    "        vis.add((0,0))\n",
    "        while quene:\n",
    "            k=len(quene)\n",
    "            while k:\n",
    "                pos=quene.popleft()\n",
    "                if pos==(x,y):\n",
    "                    return step\n",
    "                #考虑八个方向移动\n",
    "                i,j=pos[0],pos[1]\n",
    "                cur=(i+2,j+1)\n",
    "                if cur not in vis:\n",
    "                    vis.add(cur)\n",
    "                    quene.append(cur)\n",
    "                cur=(i+1,j+2)\n",
    "                if cur not in vis:\n",
    "                    vis.add(cur)\n",
    "                    quene.append(cur)\n",
    "                cur=(i-1,j+2)\n",
    "                if cur not in vis:\n",
    "                    vis.add(cur)\n",
    "                    quene.append(cur)\n",
    "                cur=(i-2,j+1)\n",
    "                if cur not in vis:\n",
    "                    vis.add(cur)\n",
    "                    quene.append(cur)\n",
    "                cur=(i+1,j-2)\n",
    "                if cur not in vis:\n",
    "                    vis.add(cur)\n",
    "                    quene.append(cur)\n",
    "                cur=(i+2,j-1)\n",
    "                if cur not in vis:\n",
    "                    vis.add(cur)\n",
    "                    quene.append(cur)\n",
    "                cur=(i-1,j-2)\n",
    "                if cur not in vis:\n",
    "                    vis.add(cur)\n",
    "                    quene.append(cur)\n",
    "                cur=(i-2,j-1)\n",
    "                if cur not in vis:\n",
    "                    vis.add(cur)\n",
    "                    quene.append(cur)\n",
    "                k-=1\n",
    "            step+=1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
